package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

/**
 * @author Dennis Li
 * @date 2020/6/11 22:30
 */
public class SwapPairs_24 {

    public ListNode swapPairs(ListNode head) {
        // 哑结点代替头部，可以更换头部结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode pre = dummy;
        while (head != null && head.next != null) {
            ListNode l1 = head, l2 = head.next;

            // 中间结点
            pre.next = l2;
            l1.next = l2.next;
            l2.next = l1;

            // 前移指针
            pre = l1;
            head = l1.next;
        }

        return dummy.next;
    }

    public ListNode swapNodes(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }

    static class Solution {
        public ListNode swapNodes(ListNode head) {
            // 递归实现 -- 注意定义
            if (head == null || head.next == null) {
                return head;
            }
            ListNode next = head.next;
            // 这里要使用递归 -- 因为交换后head之后要包含剩余的所有结点
            head.next = swapNodes(next.next);
            // 交换两个节点的位置
            next.next = head;
            // 交换后新的head是next
            return next;
        }
    }



}
